#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<map>
#include<unordered_set>
#include<string>
#include<queue>
using namespace std;
//int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
//int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
//	int m = maze.size(), n = maze[0].size();
//	queue<pair<int, int>> q;
//	unordered_set<pair<int, int>> visited;
//	q.push({ entrance[0],entrance[1] });
//	visited.insert({ entrance[0],entrance[1] });
//	int ret = 0;
//	while (!q.empty())
//	{
//		ret++;
//		int sz = q.size();
//		for (int i = 0; i < sz; i++)
//		{
//			auto [a, b] = q.front();
//			q.pop();
//			for (int k = 0; k < 4; k++)
//			{
//				int x = a + dx[k], y = b + dy[k];
//				if (x >= 0 && x < m && y >= 0 && y < n &&
//					maze[x][y] == '.' && !visited.count({ x,y }))
//				{
//					visited.insert({ x,y });
//					q.push({ x,y });
//				}
//			}
//		}
//	}
//	return ret;
//}
int m, n;
int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
int bfs(vector<vector<int>>& forest, int bx, int by, int ex, int ey)
{
	if (bx == ex && by == ey)
		return 0;
	vector<vector<bool>> visited(m, vector<bool>(n));
	queue<pair<int, int>> q;
	q.push({ bx,by });
	visited[bx][by] = true;
	int ret = 0;
	while (!q.empty())
	{
		ret++;
		int sz = q.size();
		for (int i = 0; i < sz; i++)
		{
			auto& [a, b] = q.front();
			q.pop();
			for (int k = 0; k < 4; k++)
			{
				int x = a + dx[k], y = b + dy[k];
				if (x >= 0 && x < m && y >= 0 && y < n &&
					visited[x][y] == false && forest[x][y] != 0)
				{
					if (x == ex && y == ey)
						return ret;
					q.push({ x,y });
					visited[x][y] = true;
				}
			}
		}
	}
	return -1;
}
int cutOffTree(vector<vector<int>>& forest) {
	m = forest.size(), n = forest[0].size();
	map<int, pair<int, int>> hash;
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			if (forest[i][j] != 0)
				hash[forest[i][j]] = { i,j };
	int x = hash.begin()->first;
	int ret = 0;
	int bx = 0, by = 0;
	for (auto& [a, b] : hash)
	{
		int ex = b.first, ey = b.second;
		int path = bfs(forest, bx, by, ex, ey);
		if (path == -1)
			return -1;
		ret += path;
		bx = ex, by = ey;
	}
	return ret;
}
int main()
{
	vector<vector<int>> forest = { {1,2,3},{0,0,4},{7,6,5} };
	cutOffTree(forest);
	return 0;
}